Search

We look at both the \emph{group labeling lights out game} and the \emph{neighborhood lights out game}. Our main focus is to determine necessary and sufficient conditions for when the group labeling lights out game on path graphs, cycle graphs, and complete bipartite graphs can be won for every possible initial labeling. In the process of solving this problem, we demonstrate a new proof for when the neighborhood lights out game on complete bipartite graphs can be won for every possible initial labeling.

The concept of graph flattenability, initially formalized by Belk and Connelly and later expanded by Sitharam and Willoughby, extends the question of embedding finite metric spaces into a given normed space. A finite simple graph $G=(V,E)$ is said to be $(X,Y)$-flattenable if any set of induced edge lengths from an embedding of $G$ into a normed space $Y$ can also be realised by an embedding of $G$ into a normed space $X$. This property, being minor-closed, can be characterized by a finite list of forbidden minors. Following the establishment of fundamental results about $(X,Y)$-flattenability, we identify sufficient conditions under which it implies independence with respect to the associated rigidity matroids for $X$ and $Y$. We show that the spaces $\ell_2$ and $\ell_\infty$ serve as two natural extreme spaces of flattenability and discuss $(X, \ell_p )$-flattenability for varying $p$. We provide a complete characterization of $(X,Y)$-flattenable graphs for the specific case when $X$ is 2-dimensional and $Y$ is infinite-dimensional., Comment: 21 pages, 3 figures

We define a "shifted analogue" $\mathrm{SH}_n$ of the parking function symmetric function $\mathrm{PF}_n$. The expansion of $\mathrm{SH}_n$ in terms of three bases for shifted symmetric functions is explicitly described. We don't know a shifted analogue for parking functions themselves, but some desirable properties of such an analogue are discussed., Comment: 10 pages

Perfect state transfer has great importance due to its applications in quantum information processing, quantum communication networks and cryptography. In this paper, we study the existence of perfect state transfer on Cayley graphs over the group V8n. we present some necessary and sufficient conditions for the existence of perfect state transfer on Cay(V8n; S).

In a distributed storage system serving hot data, the data recovery performance becomes important, captured e.g. by the service rate. We give partial evidence for it being hardest to serve a sequence of equal user requests (as in PIR coding regime) both for concrete and random user requests and server contents. We prove that a constant request sequence is locally hardest to serve: If enough copies of each vector are stored in servers, then if a request sequence with all requests equal can be served then we can still serve it if a few requests are changed. For random iid server contents, with number of data symbols constant (for simplicity) and the number of servers growing, we show that the maximum number of user requests we can serve divided by the number of servers we need approaches a limit almost surely. For uniform server contents, we show this limit is 1/2, both for sequences of copies of a fixed request and of any requests, so it is at least as hard to serve equal requests as any requests. For iid requests independent from the uniform server contents the limit is at least 1/2 and equal to 1/2 if requests are all equal to a fixed request almost surely, confirming the same. As a building block, we deduce from a 1952 result of Marshall Hall, Jr. on abelian groups, that any collection of half as many requests as coded symbols in the doubled binary simplex code can be served by this code. This implies the fractional version of the Functional Batch Code Conjecture that allows half-servers., Comment: 13 pages

In 1961, Dirac showed that chordal graphs are exactly the graphs that can be constructed from complete graphs by a sequence of clique-sums. In an earlier paper, by analogy with Dirac's result, we introduced the class of $GF(q)$-chordal matroids as those matroids that can be constructed from projective geometries over $GF(q)$ by a sequence of generalized parallel connections across projective geometries over $GF(q)$. Our main result showed that when $q=2$, such matroids have no induced minor in $\{M(C_4),M(K_4)\}$. In this paper, we show that the class of $GF(2)$-chordal matroids coincides with the class of binary matroids that have none of $M(K_4)$, $M^*(K_{3,3})$, or $M(C_n)$ for $n\geq 4$ as a flat. We also show that $GF(q)$-chordal matroids can be characterized by an analogous result to Rose's 1970 characterization of chordal graphs as those that have a perfect elimination ordering of vertices.

For an $n$-tuple $s$ of non-negative integers, the $s$-weak order is a lattice structure on $s$-trees, generalizing the weak order on permutations. We first describe the join irreducible elements, the canonical join representations, and the forcing order of the $s$-weak order in terms of combinatorial objects, generalizing the arcs, the non-crossing arc diagrams, and the subarc order for the weak order. We then extend the theory of shards and shard polytopes to construct geometric realizations of the $s$-weak order and all its lattice quotients as polyhedral complexes, generalizing the quotient fans and quotientopes of the weak order., Comment: 49 pages, 33 figures

Let $C(X)$ be the ring of all continuous real valued functions defined on a completely regular Hausdorff topological space $X$. The zero-set intersection graph $\Gamma (C(X))$ of $C(X)$ is a simple graph with vertex set all non units of $C(X)$ and two vertices are adjacent if the intersection of the zero sets of the functions is non empty. In this paper, we study the zero-set intersection graph of $C(X)$ and its line graph. We show that if $X$ has more than two points, then these graphs are connected with diameter and radius 2. We show that the girth of the graph is 3 and the graphs are both triangulated and hypertriangulated. We find the domination number of these graphs and finally we prove that $C(X)$ is a von Neuman regular ring if and only if $C(X)$ is an almost regular ring and for all $f \in V(\Gamma (C(X)))$ there exists $g \in V(\Gamma(C(X)))$ such that $Z(f) \cap Z(g) = \phi$ and $\{f, g\}$ dominates $\Gamma(C(X))$. Finally, we derive some properties of the line graph of $\Gamma (C(X))$.

The shrinking operation converts a hypergraph into a graph by choosing, from each hyperedge, two endvertices of a corresponding graph edge. A hypertree is a hypergraph which can be shrunk to a tree on the same vertex set. Klimo\v{s}ov\'{a} and Thomass\'{e} [J. Combin. Theory Ser. B 156 (2022), 250--293] proved (as a tool to obtain their main result on edge-decompositions of graphs into paths of equal length) that any rank $3$ hypertree $T$ can be shrunk to a tree where the degree of each vertex is at least $1/100$ times its degree in $T$. We prove a stronger and a more general bound, replacing the constant $1/100$ with $1/2k$ when the rank is $k$. In place of entropy compression (used by Klimo\v{s}ov\'{a} and Thomass\'{e}), we use a hypergraph orientation lemma combined with a characterisation of edge-coloured graphs admitting rainbow spanning trees.

The upper tail problem in a sparse Erd\H{o}s-R\'enyi graph asks for the probability that the number of copies of some fixed subgraph exceeds its expected value by a constant factor. We study the analogous problem for oriented subgraphs in directed random graphs. By adapting the proof of Cook, Dembo, and Pham, we reduce this upper tail problem to the asymptotic of a certain variational problem over edge weighted directed graphs. We give upper and lower bounds for the solution to the corresponding variational problem, which differ by a constant factor of at most $2$. We provide a host of subgraphs where the upper and lower bounds coincide, giving the solution to the upper tail problem. Examples of such digraphs include triangles, stars, directed $k$-cycles, and balanced digraphs., Comment: 18 pages

A topological interlocking assembly consists of rigid blocks together with a fixed frame, such that any subset of blocks is kinematically constrained and therefore cannot be removed from the assembly. In this paper we pursue a modular approach to construct (non-convex) interlocking blocks by combining finitely many tetrahedra and octahedra. This gives rise to polyhedra whose vertices can be described by the tetrahedral-octahedral honeycomb, also known as tetroctahedrille. We show that the resulting interlocking blocks are very versatile and allow many possibilities to form topological interlocking assemblies consisting of copies of a single block. We formulate a generalised construction of some of the introduced blocks to construct families of topological interlocking blocks. Moreover, we demonstrate a geometric application by using the tetroctahedrille to approximate given geometric objects. Finally, we show that given topological interlocking assemblies can be deformed continuously in order to obtain new topological interlocking assemblies., Comment: Keywords: Topological interlocking, Space Fillings, Triangulations, Origami, Approximations

The mean color number of an $n$-vertex graph $G$, denoted by $\mu(G)$, is the average number of colors used in all proper $n$-colorings of $G$. For any graph $G$ and a vertex $w$ in $G$, Dong (2003) conjectured that if $H$ is a graph obtained from a graph $G$ by deleting all but one of the edges which are incident to $w$, then $\mu(G)\geq \mu(H)$; and also conjectured that $\mu(G)\geq \mu((G-w)\cup K_1)$. We prove that there is an infinite family of counterexamples to these two conjectures., Comment: 5 pages

We prove that if a graph contains the complete bipartite graph $K_{134, 12}$ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contains $K_{3, 4}$ as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a \emph{theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$, each of length at least two, such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number, or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels)., Comment: 25 pages, 12 figures

In I981, Uchimura studied a divisor generating $q$-series that has applications in probability theory and in the analysis of data structures, called heaps. Mainly, he proved the following identity. For $|q|<1$, \begin{equation*} \sum_{n=1}^\infty n q^n (q^{n+1})_\infty =\sum_{n=1}^{\infty} \frac{(-1)^{n-1} q^{\frac{n(n+1)}{2} } }{(1-q^n) ( q)_n } = \sum_{n=1}^{\infty} \frac{ q^n }{1-q^n}. \end{equation*} Over the years, this identity has been generalized by many mathematicians in different directions. Uchimura himself in 1987, Dilcher (1995), Andrews-Crippa-Simon (1997), and recently Gupta-Kumar (2021) found a generalization of the aforementioned identity. Any generalization of the right most expression of the above identity, we name as divisor-type sum, whereas a generalization of the middle expression we say Ramanujan-type sum, and any generalization of the left most expression we refer it as Uchimura-type sum. Quite surprisingly, Simon, Crippa and Collenberg (1993) showed that the same divisor generating function has a connection with random acyclic digraphs. One of the main themes of this paper is to study these different generalizations and present a unified theory. We also discuss applications of these generalized identities in probability theory for the analysis of heaps and random acyclic digraphs., Comment: 33 pages, comments are welcome!

We show that all invertible $n \times n$ matrices over any finite field $\mathbb{F}_q$ can be generated in a Gray code fashion. More specifically, there exists a listing such that (1) each matrix appears exactly once, and (2) two consecutive matrices differ by adding or subtracting one row from a previous or subsequent row, or by multiplying or diving a row by the generator of the multiplicative group of $\mathbb{F}_q$. This even holds if the addition and subtraction of each row is allowed to some specific rows satisfying a certain mild condition. Moreover, we can prescribe the first and the last matrix if $n\ge 3$, or $n=2$ and $q>2$. In other words, the corresponding flip graph on all invertible $n \times n$ matrices over $\mathbb{F}_q$ is Hamilton connected if it is not a cycle., Comment: 20 pages, 6 figures

Let $s$ be West's deterministic stack-sorting map. A well-known result (West) is that any length $n$ permutation can be sorted with $n-1$ iterations of $s.$ In 2020, Defant introduced the notion of highly-sorted permutations -- permutations in $s^t(S_n)$ for $t \lessapprox n-1.$ In 2023, Choi and Choi extended this notion to generalized stack-sorting maps $s_{\sigma},$ where we relax the condition of becoming sorted to the analogous condition of becoming periodic with respect to $s_{\sigma}.$ In this work, we introduce the notion of minimally-sorted permutations $\mathfrak{M}_n$ as an antithesis to Defant's highly-sorted permutations, and show that $\text{ord}_{s_{123, 132}}(S_n) = 2 \lfloor \frac{n-1}{2} \rfloor,$ strengthening Berlow's 2021 classification of periodic points.

A given subset $A$ of natural numbers is said to be complete if every element of $\N$ is the sum of distinct terms taken from $A$. This topic is strongly connected to the knapsack problem which is known to be NP complete. The main goal of the paper is to study the structure of subset sums in a higher dimension. We show 'dense' sets and generalized arithmetic progrssions in subset sums of certain sets., Comment: 21 pages, comments are welcome

Extending Sparks's theorem, we determine the cardinality of the lattice of $(C_1,C_2)$-clonoids of Boolean functions in the cases where the target clone $C_2$ is the clone of projections. Moreover, we explicitly describe the $(C_1,C_2)$-clonoids of Boolean functions in the cases where the source clone $C_1$ is one of the four clones of monotone functions or contains the discriminator function., Comment: 38 pages

We establish the $e$-positivity of all cycle-chord graphs by using the composition method that is developed by Zhou and the author very recently. Our technique is not only applicable to all cycle-chords, but also much simpler than the $(e)$-positivity method that is used for handling cycle-chords with girth at most $4$., Comment: 5 pages, 1 figure

We show that any graded digraph $D$ on $n$ vertices with maximum degree $\Delta$ has an oriented Ramsey number of at most $C^\Delta n$ for some absolute constant $C > 1$, improving upon a recent result of Fox, He, and Wigderson. In particular, this implies that oriented grids in any fixed dimension have linear oriented Ramsey numbers, and gives a polynomial bound on the oriented Ramsey number of the hypercube. We also show that this result is essentially best possible, in that there exist graded digraphs on $n$ vertices with maximum degree $\Delta$ such that their oriented Ramsey number is at least $c^\Delta n$ for some absolute constant $c > 1$., Comment: 20 pages

We introduce and study a generalization $s_{(\mu|\lambda)}$ of the Schur functions called the almost symmetric Schur functions. These functions simultaneously generalize the finite variable key polynomials and the infinite variable Schur functions. They form a homogeneous basis for the space of almost symmetric functions and are defined using a family of recurrences involving the isobaric divided difference operators and limits of Weyl symmetrization operators. The $s_{(\mu|\lambda)}$ are the $q=t=0$ specialization of the stable limit non-symmetric Macdonald functions $\widetilde{E}_{(\mu|\lambda)}$ defined by the author in previous work. We find a combinatorial formula for these functions simultaneously generalizing well known formulas for the Schur functions and the key polynomials. Further, we prove positivity results for the coefficients of the almost symmetric Schur functions expanded into the monomial basis and into the monomial-Schur basis of the space of almost symmetric functions. The latter positivity result follows after realizing the almost symmetric Schur functions $s_{(\mu|\lambda)}$ as limits of characters of representations of parabolic subgroups in type $GL.$, Comment: 23 pages

The enhanced power graph of a group $G$ is a graph with vertex set $G,$ where two distinct vertices $x$ and $y$ are adjacent if and only if there exists an element $w$ in $G$ such that both $x$ and $y$ are powers of $w.$ In this paper, we determine the vertex connectivity of the enhanced power graph of any finite nilpotent group., Comment: 11 pages, Comments are welcome. arXiv admin note: text overlap with arXiv:2108.05175

The unitary Cayley graph has vertex set $\Zl_n =\{0,1, \hdots ,n-1\}$, where two vertices $u$ and $v$ are adjacent if $\text{gcd}(u - v, n) = 1$. We focus on the periodicity and perfect state transfer of Grover walk on the unitary Cayley graphs. We completely characterize which unitary Cayley graphs are periodic. From our results, we find infinitely many new periodic graphs. We prove that periodicity is a necessary condition for perfect state transfer on an integral vertex-transitive graph, and we provide a simple criterion to characterize perfect state transfer on circulant graphs in terms of its adjacency spectrum. Using these, we prove only three graphs in a class of unitary Cayley graphs exhibit perfect state transfer. Also, we provide a spectral characterization of the periodicity of Grover walk on any integral regular graphs.

The computational complexity of tiling finite simply connected regions with a fixed set of tiles is studied in this paper. We show that the problem of tiling simply connected regions with a fixed set of $23$ Wang tiles is NP-complete. As a consequence, the problem of tiling simply connected regions with a fixed set of $111$ rectangles is NP-complete. Our results improve that of Igor Pak and Jed Yang by using fewer numbers of tiles. Notably in the case of Wang tiles, the number has decreased by more than one third from $35$ to $23$.

In this paper, we compute the dual $F$-signatures of certain toric rings by using combinatorial techniques. Specifically, we calculate the dual $F$-signatures of Veronese subrings of polynomial rings. Moreover, we give an upper bound for the dual $F$-signatures of Segre products of polynomial rings and show that this upper bound is attained in some cases., Comment: 14 pages

We prove a descriptive version of Brooks's theorem for directed graphs. In particular, we show that, if $D$ is a Borel directed graph on a standard Borel space $X$ such that the maximum degree of each vertex is at most $d \geq 3$, then unless $D$ contains the complete symmetric directed graph on $d + 1$ vertices, $D$ admits a $\mu$-measurable $d$-dicoloring with respect to any Borel probability measure $\mu$ on $X$, and $D$ admits a $\tau$-Baire-measurable $d$-dicoloring with respect to any Polish topology $\tau$ compatible with the Borel structure on $X$. We also prove a definable version of Gallai's theorem on list dicolorings for directed graphs by showing that any Borel directed graph of bounded degree whose connected components are not Gallai trees is Borel degree-list-dicolorable., Comment: 19 pages

In this paper, we explore the application of a particular genetic algorithm, the Rank Genetic Algorithm (Rank GA), to address a graph theory problem. The Rank GA was introduced to address the problem of graph coloring, exploring into the specialized field of Chromatic Graph Theory. We successfully improved several of the previously known lower bounds. To validate the effectiveness of these new bounds, we performed an analytical approximation, confirming their validity. The findings underscore the interdisciplinary impact of the use of genetic algorithms in theoretical mathematical research., Comment: 15 pages, 3 figures

The Ramsey-Tur\'an problem for $K_p$ asks for the maximum number of edges in an $n$-vertex $K_p$-free graph with independence number $o(n)$. In a natural generalization of the problem, cliques larger than the edge $K_2$ are counted. Let {\bf RT}$(n,\#K_q,K_p,o(n))$ denote the maximum number of copies of $K_q$ in an $n$-vertex $K_p$-free graph with independence number $o(n)$. Balogh, Liu and Sharifzadeh determined the asymptotics of {\bf RT}$(n,\# K_3,K_p,o(n))$. In this paper we will establish the asymptotics for counting copies of $K_4$, $K_5$, and for the case $p \geq 5q$. We also provide a family of counterexamples to a conjecture of Balogh, Liu and Sharifzadeh.

A kernel in a digraph is an independent and absorbent subset of its vertex set. A digraph is critical kernel imperfect if it does not have a kernel, but every proper induced subdigraph does. In this article, we characterize asymmetrical $4$-quasi-transitive and $4$-transitive digraphs, as well as $2$-anti-transitive, and asymmetrical $4$-anti-transitive digraphs with bounded diameter, which are critical kernel imperfect., Comment: 20 pages

The distributions of the $m$-th longest runs of multivariate random sequences are considered. For random sequences made up of $k$ kinds of letters, the lengths of the runs are sorted in two ways to give two definitions of run length ordering. In one definition, the lengths of the runs are sorted separately for each letter type. In the second definition, the lengths of all the runs are sorted together. Exact formulas are developed for the distributions of the m-th longest runs for both definitions. The derivations are based on a two-step method that is applicable to various other runs-related distributions, such as joint distributions of several letter types and multiple run lengths of a single letter type.

By using the matrix formulation of the two-step approach to distributions of patterns in random sequences, recurrence and explicit formulas for the generating functions of successions in random permutations of arbitrary multisets are derived. Explicit formulas for the mean and variance are also obtained.

By using the matrix formulation of the two-step approach to the distributions of runs, a recursive relation and an explicit expression are derived for the generating function of the joint distribution of rises and falls for multivariate random sequences in terms of generating functions of individual letters, from which the generating functions of the joint distribution of rises, falls, and number of runs are obtained. An explicit formula for the joint distribution of rises and falls with arbitrary specification is also obtained.

Subspace codes have recently been used for error correction in random network coding. In this work, we focus on one-orbit cyclic subspace codes. If $S$ is an $\mathbb{F}_q$-subspace of $\mathbb{F}_{q^n}$, then the one-orbit cyclic subspace code defined by $S$ is \[ \mathrm{Orb}(S)=\{\alpha S \colon \alpha \in \mathbb{F}_{q^n}^*\}, \]where $\alpha S=\lbrace \alpha s \colon s\in S\rbrace$ for any $\alpha\in \mathbb{F}_{q^n}^*$. Few classification results of subspace codes are known, therefore it is quite natural to initiate a classification of cyclic subspace codes, especially in the light of the recent classification of the isometries for cyclic subspace codes. We consider three-dimensional one-orbit cyclic subspace codes, which are divided into three families: the first one containing only $\mathrm{Orb}(\mathbb{F}_{q^3})$; the second one containing the optimum-distance codes; and the third one whose elements are codes with minimum distance $2$. We study inequivalent codes in the latter two families., Comment: Accepted to the 2024 IEEE International Symposium on Information Theory (ISIT 2024)

Fix $h\geq 2$, and let $b_1$ , $\ldots$, $b_h$ be not necessarily distinct positive integers with $\gcd = 1$. For any subset $A\subseteq \mathbb{N}$, write $r_{A}(n)$ ($n\geq 0$) for the number of solutions $(k_1,\ldots,k_h)\in A^h$ to \[ b_1 k_1 + \cdots + b_h k_h = n. \] For which functions $F$ with $F(n) \leq r_{\mathbb{N}}(n)$ can we find $A\subseteq \mathbb{N}$ such that $r_{A}(n)\sim F(n)$? We show that if $F$ is regularly varying, then there exists such an $A$ provided $\lim\limits_{n\to\infty} F(n)/\log n = \infty$. If one only requires $r_{A}(n) \asymp F(n)$, we show there exists such an $A$ for every increasing $F$ satisfying $F(2x) \ll F(x)$ and $\liminf\limits_{n\to\infty} F(n)/\log n > 0$. Lastly, we give a probabilistic heuristic for the following statement: if $A\subseteq \mathbb{N}$ is such that $\limsup\limits_{n\to\infty} r_{A}(n)/\log n < 1$, then $r_{A}(n) = 0$ for infinitely many $n$., Comment: 23 pages

We introduce the notion of P-polynomial coherent configurations and show that they can have at most two fibres. We then introduce a class of two-fibre coherent configurations which have two distinguished bases for the coherent algebra, similar to the Bose-Mesner algebra of an association scheme. Examples of these bipartite coherent configurations include the P-polynomial class of distance-biregular graphs, as well as quasi-symmetric designs and strongly regular designs., Comment: 34 pages

Zero forcing in graphs is a coloring process where a colored vertex can force its unique uncolored neighbor to be colored. A zero forcing set is a set of initially colored vertices capable of eventually coloring all vertices of the graph. In this paper, we focus on the numbers $z(G; i)$, which is the number of zero forcing sets of size $i$ of the graph $G$. These numbers were initially studied by Boyer et al. where they conjectured that for any graph $G$ on $n$ vertices, $z(G; i) \leq z(P_n; i)$ for all $i \geq 1$ where $P_n$ is the path graph on $n$ vertices. The main aim of this paper is to show that several classes of graphs, including outerplanar graphs and threshold graphs, satisfy this conjecture. We do this by studying various graph operations and examining how they affect the number of zero forcing sets., Comment: 17 pages, 17 figures

An $\mathbb{F}_q$- linear set $L=L_U$ of $\Lambda=\mathrm{PG}(V, \mathbb{F}_{q^n}) \cong \mathrm{PG}(r-1,q^n)$ is a set of points defined by non-zero vectors of an $\mathbb{F}_q$-subspace $U$ of $V$. The integer $\dim_{\mathbb{F}_q} U$ is called the rank of $L$. In [G. Lunardon, O. Polverino: Translation ovoids of orthogonal polar spaces. Forum Math. 16 (2004)], it was proven that any $\mathbb{F}_q$-linear set $L$ of $\Lambda$ of rank $u$ such that $\langle L \rangle=\Lambda$ is either a canonical subgeometry of $\Lambda$ or there are a $(u-r-1)$-dimensional subspace $\Gamma$ of $\mathrm{PG}(u-1,q^n) \supset \Lambda$ disjoint from $\Lambda$ and a canonical subgeometry $\Sigma \cong \mathrm{PG}(u-1,q)$ disjoint from $\Gamma$ such that $L$ is the projection of $\Sigma$ from $\Gamma$ onto $\Lambda$. The subspace $\Gamma$ is called the vertex of the projection. In this article, we will show a method to reconstruct the vertex $\Gamma$ for a peculiar class of linear sets of rank $u = n(r - 1)$ in $\mathrm{PG}(r - 1, q^n)$ called evasive linear sets. Also, we will use this result to characterize some families of linear sets of the projective line $\mathrm{PG}(1,q^n)$ introduced from 2018 onward, by means of certain properties of their projection vertices, as done in [B. Csajb\'{o}k, C. Zanella: On scattered linear sets of pseudoregulus type in $\mathrm{PG}(1, q^t)$, Finite Fields Appl. 41 (2016)] and in [C. Zanella, F. Zullo: Vertex properties of maximum scattered linear sets of $\mathrm{PG}(1, q^n)$. Discrete Math. 343(5) (2020)].

This study explores the relationship between hypergraph automorphisms and the spectral properties of matrices associated with hypergraphs. For an automorphism $f$, an \( f \)-compatible matrices capture aspects of the symmetry, represented by \( f \), within the hypergraph. First, we explore rotation, a specific kind of automorphism and find that the spectrum of any matrix compatible with a rotation can be decomposed into the spectra of smaller matrices associated with that rotation. We show that the spectrum of any \(f\)-compatible matrix can be decomposed into the spectra of smaller matrices associated with the component rotations comprising \( f \). Further, we study a hypergraph symmetry termed unit-automorphism, which induces bijections on the hyperedges, though not necessarily on the vertex set. We show that unit automorphisms also lead to the spectral decomposition of compatible matrices.

The Hamming graph $H(n,q)$ is defined on the vertex set $[q]^n$ and two vertices are adjacent if and only if they differ in precisely one coordinate. Alon \cite{Alon} proved that the burning number of $H(n,2)$ is $\lceil\frac n2\rceil+1$. In this note we show that the burning number of $H(n,q)$ is $(1-\frac 1q)n+O(\sqrt{n\log n})$ for fixed $q\geq 2$ and $n\to\infty$.

We study the distribution of fringe trees in Patricia tries and compressed binary search trees; both cases are random binary trees that have been compressed by deleting vertices of outdegree 1 so that they are random full binary trees. The main results are central limit theorems for the number of fringe trees of a given type, which imply quenched and annealed limit results for the fringe tree distribution; for Patricia tries, this is complicated by periodic oscillations in the usual manner. We also consider extended fringe trees. The results are derived from earlier results for uncompressed tries and binary search trees. In the case of compressed binary search trees, it seems difficult to give a closed formula for the asymptotic fringe tree distribution, but we provide a recursion and give examples., Comment: 28 pages

Let $H_n^{(3)}$ be a 3-uniform linear hypergraph, i.e. any two edges have at most one vertex common. A special hypergraph, {\em wicket}, is formed by three rows and two columns of a $3 \times 3$ point matrix. In this note, we give a new lower bound on the Tur\'an number of wickets using estimates on cap sets.

We present both bijective and automated approaches to Abel-type sums, dear to Dominique Foata., Comment: 9 pages. Dedicated to Dominique Foata on his forthcoming 90th birthday

We establish upper bounds on the size of the largest subset of $\{1,2,\dots,N\}$ lacking nonzero differences of the form $h(p_1,\dots,p_{\ell})$, where $h\in \mathbb{Z}[x_1,\dots,x_{\ell}]$ is a fixed polynomial satisfying appropriate conditions and $p_1,\dots,p_{\ell}$ are prime. The bounds are of the same type as the best-known analogs for unrestricted integer inputs, due to Bloom-Maynard and Arala for $\ell=1$, and to the authors for $\ell \geq 2$., Comment: 22 pages. arXiv admin note: text overlap with arXiv:2006.15400

This paper considers the existence of short synchronizing words in deterministic finite automata (DFAs). In particular, we define a general strategy, which we call the \emph{cornering strategy}, for generating short synchronizing words in well-structured DFAs. We show that a DFA is synchronizable if and only if this strategy can be applied. Using the cornering strategy, we prove that all DFAs consisting of $n$ points in $\mathbb{R}^d$ with bidirectional connected edge sets in which each edge $(\mb x, \mb y)$ is labeled $\mb y - \mb x$ are synchronizable. We also give sufficient conditions for such DFAs to have synchronizing words of length at most $(n-1)^2$ and thereby satisfy \v{C}ern\'y's conjecture. Using similar ideas, we generalise a result of Ananichev and Volkov \cite{ananichev2004synchronizing} from monotonic automata to a wider class of DFAs admitting well-behaved partial orders. Finally, we consider how the cornering strategy can be applied to the problem of simultaneously synchronizing a DFA $G$ to an initial state $u$ and a DFA $H$ to an initial state $v$. We do not assume that DFAs $G$ and $H$ or states $u$ and $v$ are related beyond sharing the same edge labels., Comment: 17 pages, 6 figures

We establish a connection between problems studied in rigidity theory and matroids arising from linear algebraic constructions like tensor products and symmetric products. A special case of this correspondence identifies the problem of giving a description of the correctable erasure patterns in a maximally recoverable tensor code with the problem of describing bipartite rigid graphs or low-rank completable matrix patterns. Additionally, we relate dependencies among symmetric products of generic vectors to graph rigidity and symmetric matrix completion. With an eye toward applications to computer science, we study the dependency of these matroids on the characteristic by giving new combinatorial descriptions in several cases, including the first description of the correctable patterns in an (m, n, a=2, b=2) maximally recoverable tensor code.

Courcelle's Theorem is an important result in graph theory, proving the existence of linear-time algorithms for many decision problems on graphs whose tree-width is bounded by a constant. The purpose of this text is twofold: to provide an explanation and step-by-step proof of Courcelle's Theorem as applied to graphs of tree-width bounded by a constant, and to show explicitly (on the example of path-width) how to apply the same principles to other graph classes. We present these topics in a way that does not assume any particular knowledge on the part of the reader except a basic understanding of mathematics and possibly the fundamentals of graph theory. Our hope is to make the topic accessible to a broader mathematical audience, to which end we have included extensive explanations and pretty pictures., Comment: 252 pages, master's thesis

We construct a new family of graded representations $\widetilde{W}_{\lambda}$ for the positive elliptic Hall algebra $\mathcal{E}^{+}$ indexed by Young diagrams $\lambda$ which generalize the standard $\mathcal{E}^{+}$ action on symmetric functions. These representations have homogeneous bases of eigenvectors for the action of the Macdonald element $P_{0,1} \in \mathcal{E}^{+}$ with distinct $\mathbb{Q}(q,t)$-rational spectrum generalizing the symmetric Macdonald functions. The analysis of the structure of these representations exhibits interesting combinatorics arising from the stable limits of periodic standard Young tableaux. We find an explicit combinatorial rule for the action of the multiplication operators $e_r[X]^{\bullet}$ generalizing the Pieri rule for symmetric Macdonald functions. We will also naturally obtain a family of interesting $(q,t)$ product-series identities which come from keeping track of certain combinatorial statistics associated to periodic standard Young tableaux., Comment: This is the complete version of the author's accepted FPSAC24 extended abstract arXiv:2310.10249; 52 pages

We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erd\H{o}s-R\'enyi random graph $G(n,p)$. Recently Acan and Kahn showed that the largest such family contains only $O(n^2/(\log{n})^3)$ cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, $\Omega(n^2/(\log{n})^3)$, by considering a random graph process which sequentially selects and deletes near-maximal cliques. To analyse this process we use the Differential Equation Method. We also give a new proof of the upper bound $O(n^2/(\log{n})^3)$ and discuss the problem of the precise size of the largest such clique packing., Comment: 43 pages

The problems that we consider in this paper are as follows. Let A and B be 2x2 matrices (over reals). Let w(A, B) be a word of length n. After evaluating w(A, B) as a product of matrices, we get a 2x2 matrix, call it W. What is the largest (by the absolute value) possible entry of W, over all w(A, B) of length n, as a function of n? What is the expected absolute value of the largest (by the absolute value) entry in a random product of n matrices, where each matrix is A or B with probability 0.5? What is the Lyapunov exponent for a random matrix product like that? We give partial answer to the first of these questions and an essentially complete answer to the second question. For the third question (the most difficult of the three), we offer a very simple method to produce an upper bound on the Lyapunov exponent in the case where all entries of the matrices A and B are nonnegative., Comment: 10 pages. Comments are welcome

Extremal Type II $\mathbb{Z}_{8}$-codes are a class of self-dual $\mathbb{Z}_{8}$-codes with Euclidean weights divisible by $16$ and the largest possible minimum Euclidean weight for a given length. We introduce a doubling method for constructing a Type II $\mathbb{Z}_{2k}$-code of length $n$ from a known Type II $\mathbb{Z}_{2k}$-code of length $n$. Based on this method, we develop an algorithm to construct new extremal Type II $\mathbb{Z}_8$-codes starting from an extremal Type II $\mathbb{Z}_8$-code of type $(\frac{n}{2},0,0)$ with an extremal $\mathbb{Z}_4$-residue code and length $24, 32$ or $40$. We construct at least ten new extremal Type II $\mathbb{Z}_8$-codes of length $32$ and type $(15,1,1)$. Extremal Type II $\mathbb{Z}_8$-codes of length $32$ of this type were not known before. Moreover, the binary residue codes of the constructed extremal $\mathbb{Z}_8$-codes are optimal $[32,15]$ binary codes., Comment: 12 pages. arXiv admin note: text overlap with arXiv:2310.14080